
package sort.SelectSort_HeapSort;


public class HeapSort {
   public void sort(int[] a){
	   for(int i=((a.length-2)/2);i>=0;i--){
		   heapAjust(a,a.length,i);
	   }
	   int len=a.length;
	   while(len>0){
		  System.out.print(a[0]+" ");
		   a[0]=a[len-1];
		   len--;
		   heapAjust(a,len,0);
	  }  
   }
   private void heapAjust(int[] a ,int len ,int k){
	   int kl=2*k+1;int kr=2*k+2;
	   if(kl>=len && kr>=len){return;}	   
	   int al=Integer.MAX_VALUE;
	   int ar=Integer.MAX_VALUE;
	   if(kl<len){al=a[kl];}
       if(kr<len){ar=a[kr];}   
       if(a[k]<=al && a[k]<=ar){return;}
	   if(al<ar){
		   int tmp=a[k];a[k]=a[kl];a[kl]=tmp;
		   heapAjust(a,len,kl);
	   }else{
		   int tmp=a[k];a[k]=a[kr];a[kr]=tmp;
		   heapAjust(a,len,kr);
	   } 
   }
}
